#include <thread>

#include "./CentralCache.h"
#include "./PageCache.h"

namespace MemoryPool
{
    CentralCache &CentralCache::getInstance()
    {
        static CentralCache instance{};
        return instance;
    }

    CentralCache::CentralCache()
    {
        for (auto &ptr : this->freeRanges_)
        {
            ptr.store(nullptr, std::memory_order_relaxed);
        }

        for (auto &lock : this->locks_)
        {
            lock.clear();
        }
    }

    void *CentralCache::allocRange(const size_t needRangeIndex)
    {
        // 索引检查，大于等于说明申请内存过大，上层应直接向系统申请
        // 因为内存池对大内存申请不友好，会占用大空间无法分配小空间
        if (needRangeIndex >= SizeManager::FREE_LIST_NUM)
        {
            return nullptr;
        }

        // 获取自旋锁
        // std::memory_order_acquire：获取锁时，所有之前的写操作都已完成
        // test_and_set()：获取锁，false成功，true失败
        while (this->locks_[needRangeIndex].test_and_set(std::memory_order_acquire))
        {
            std::this_thread::yield(); // 线程让步避免忙等待，放弃当前CPU时间片，避免过度消耗CPU，
        }

        // 获取到锁
        void *resultRange{nullptr};
        try
        {
            // 尝试从中心缓存获取range
            resultRange = this->freeRanges_[needRangeIndex].load(std::memory_order_relaxed);

            if (!resultRange)
            {
                // 如果中心缓存为空，从PageCahe获取新的内存
                // 要获取到索引0，则需要0+1个，再×字节对齐数
                size_t needSize = (needRangeIndex + 1) * SizeManager::ALIGNMENT_BYTES;

                size_t needPageNum{0};
                resultRange = this->allocFromPageCache(needSize, needPageNum);
                if (!resultRange)
                {
                    this->locks_[needRangeIndex].clear(std::memory_order_release);
                    return nullptr;
                }

                // size_t blockNum = (SPAN_PAGES * PageCache::PAGE_SIZE) / needSize;
                // OPTIMIZE: 根据页数阈值计算不同的range数
                size_t rangeNum{};
                if (needPageNum == 0) // 小于32KB按照固定页数SPAN_PAGES分配的
                {
                    rangeNum = (SPAN_PAGES * PageCache::PAGE_SIZE) / needSize;
                }
                else // 否则按照指定页数分配的
                {
                    rangeNum = (needPageNum * PageCache::PAGE_SIZE) / needSize;
                }

                // 将获取的内存范围切分成小范围
                // 地址一个B，用char*操作
                char *startRange = static_cast<char *>(resultRange);

                // 注意索引+1 == 数量
                if (rangeNum > 1) // 确保至少有两个range才构建链表
                {
                    for (size_t i = 1; i < rangeNum; ++i)
                    {
                        void *curr = startRange + (i - 1) * needSize;
                        void *next = startRange + i * needSize;
                        // 注意写法：
                        // reinterpret_cast<void *>(curr) = next 是直接赋值了，修改了curr地址值，且右值无法赋值
                        // 先转换void **，解引用后得到void *指针可以指向下一个，和上一行的void*意思不一样
                        // 即curr->next = next;
                        *reinterpret_cast<void **>(curr) = next;
                    }
                    *reinterpret_cast<void **>(startRange + (rangeNum - 1) * needSize) = nullptr;

                    // 保存resultRange的下一个节点
                    void *nextRange = *reinterpret_cast<void **>(resultRange);
                    // 将resultRange与链表断开
                    *reinterpret_cast<void **>(resultRange) = nullptr;

                    // 更新中心缓存
                    // needRangeIndex在Common.h计算，对应到needSize
                    // needSize保证是8B对齐的，根据needSize划分range
                    // 更新时，needRangeIndex存的就是相应needSize大小的range链表
                    // freeRanges_[0]存的是8B链表，freeRanges_[1]存的是16B链表...
                    this->freeRanges_[needRangeIndex].store(nextRange, std::memory_order_release);
                }
                // 不够构建链表，本来也是从PageCace申请的，不需要更新this->freeRanges_
            }
            else // 直接从中央缓存获取到了
            {
                // 保存result的下一个节点
                void *nextRange = *reinterpret_cast<void **>(resultRange);
                // 将result与链表断开
                *reinterpret_cast<void **>(resultRange) = nullptr;

                // 更新中心缓存
                this->freeRanges_[needRangeIndex].store(nextRange, std::memory_order_release);
            }
        }
        catch (...)
        {
            this->locks_[needRangeIndex].clear(std::memory_order_release);
            throw;
        }

        // 释放锁
        this->locks_[needRangeIndex].clear(std::memory_order_release);
        return resultRange;
    }

    void *CentralCache::allocFromPageCache(const size_t needSize, size_t &needPageNum)
    {
        // 1. 计算实际需要的页数
        // 如果 needSize / PAGE_SIZE = 8193 / 4096 = 2
        // 2 * 4096 < 8193，分配的页数不够
        // 如果 (needSize + PAGE_SIZE - 1) / PAGE_SIZE = (8193 + 4096 - 1) / 4096 = 3
        // 3 * 4096 >= 8193，分配的页数足够
        // 所以：+ PAGE_SIZE是为了下取整除法分配足够页面，- 1是为了不至于多分配一个页
        // 也可以：needSize / PAGE_SIZE + 1，有余数才+1，否则不+1
        needPageNum = (needSize + PageCache::PAGE_SIZE - 1) / PageCache::PAGE_SIZE;

        // 2. 根据大小决定分配策略
        if (needSize <= SPAN_PAGES * PageCache::PAGE_SIZE)
        {
            // 小于等于32KB的请求，使用固定8页
            needPageNum = 0; // 作为外部调用后分range不同操作的标志
            return PageCache::getInstance().allocSpan(SPAN_PAGES);
        }
        else
        {
            // 大于32KB的请求，按实际需求分配
            return PageCache::getInstance().allocSpan(needPageNum);
        }
    }

    void CentralCache::deallocRange(void *needRangeStart, const size_t needRangeIndex, const size_t needRangeSize)
    {
        // 当索引大于等于FREE_LIST_SIZE时，说明内存过大应直接向系统归还
        if (!needRangeStart || needRangeIndex >= SizeManager::FREE_LIST_NUM)
        {
            return;
        }

        // std::memory_order_acquire：load()，读写操作，读写操作不会重排到load()前
        while (this->locks_[needRangeIndex].test_and_set(std::memory_order_acquire))
        {
            std::this_thread::yield();
        }

        try
        {
            // 找到要归还的链表的最后一个range
            void *endRange = needRangeStart;
            size_t count{1};
            while (*reinterpret_cast<void **>(endRange) != nullptr && count < needRangeSize)
            {
                endRange = *reinterpret_cast<void **>(endRange);
                ++count;
            }

            // 将归还的链表连接到中央缓存的链表头部
            void *rangeHead = this->freeRanges_[needRangeIndex].load(std::memory_order_relaxed);
            *reinterpret_cast<void **>(endRange) = rangeHead; // 将原链表头接到归还链表的尾部，头插
            // std::memory_order_release：读写操作，store()，读写操作不会重排到store()后
            this->freeRanges_[needRangeIndex].store(needRangeStart, std::memory_order_release); // 将归还的链表头设为新的链表头
        }
        catch (...)
        {
            this->locks_[needRangeIndex].clear(std::memory_order_release);
            throw;
        }

        this->locks_[needRangeIndex].clear(std::memory_order_release);
    }

    void *CentralCache::allocRange2(const size_t needRangeIndex, const size_t needRangeNum)
    {
        // 不同1
        if (needRangeIndex >= SizeManager::FREE_LIST_NUM || needRangeNum == 0)
        {
            return nullptr;
        }

        while (this->locks_[needRangeIndex].test_and_set(std::memory_order_acquire))
        {
            std::this_thread::yield();
        }

        void *resultRange{nullptr};
        try
        {
            resultRange = this->freeRanges_[needRangeIndex].load(std::memory_order_relaxed);

            // TODO: 计算本层链表range数量不够，从PageCache申请，申请后留下的要连接而不是替换本层链表
            if (!resultRange) // 没有
            {
                size_t needSize = (needRangeIndex + 1) * SizeManager::ALIGNMENT_BYTES;

                size_t needPageNum{0};
                resultRange = this->allocFromPageCache(needSize, needPageNum);
                if (!resultRange)
                {
                    this->locks_[needRangeIndex].clear(std::memory_order_release);
                    return nullptr;
                }

                size_t rangeNum{};
                if (needPageNum == 0)
                {
                    rangeNum = (SPAN_PAGES * PageCache::PAGE_SIZE) / needSize;
                }
                else
                {
                    rangeNum = (needPageNum * PageCache::PAGE_SIZE) / needSize;
                }

                // size_t totalBlocks = (SPAN_PAGES * PageCache::PAGE_SIZE) / size;
                // 不同2
                // 在实际需要和实际分配的取最小，实际分配因为要字节对齐一般是大于等于实际需要的
                size_t allocRangeNum = std::min(needRangeNum, rangeNum);

                // 不同3
                // allocRangeNum构成链表批量给上层
                // 剩下的也构成链表存在当前层
                char *startRange = static_cast<char *>(resultRange);

                if (allocRangeNum > 1)
                {
                    for (size_t i = 1; i < allocRangeNum; ++i)
                    {
                        void *curr = startRange + (i - 1) * needSize;
                        void *next = startRange + i * needSize;
                        *reinterpret_cast<void **>(curr) = next;
                    }
                    *reinterpret_cast<void **>(startRange + (allocRangeNum - 1) * needSize) = nullptr;
                }

                if (rangeNum > allocRangeNum)
                {
                    void *remainStartRange = startRange + allocRangeNum * needSize;

                    for (size_t i = allocRangeNum + 1; i < rangeNum; ++i)
                    {
                        void *curr = startRange + (i - 1) * needSize;
                        void *next = startRange + i * needSize;
                        *reinterpret_cast<void **>(curr) = next;
                    }
                    *reinterpret_cast<void **>(startRange + (rangeNum - 1) * needSize) = nullptr;

                    this->freeRanges_[needRangeIndex].store(remainStartRange, std::memory_order_release);
                }
            }
            else // 有
            {
                // 不同4
                // 从现有链表中获取指定数量的块
                void *curr = resultRange;
                void *prev = nullptr;
                size_t count{0};

                // 移动prev，prev前面和prev的返回给上层，prev后面的保留当前层
                while (curr && count < needRangeNum)
                {
                    prev = curr;
                    curr = *reinterpret_cast<void **>(curr);
                    ++count;
                }

                if (prev) // 当前链表上的内存节点大于needRangeNum时需要用到，返回给上层的尾节点置空断开
                {
                    *reinterpret_cast<void **>(prev) = nullptr;
                }

                this->freeRanges_[needRangeIndex].store(curr, std::memory_order_release); // 剩下的头节点保留在当前层
            }
        }
        catch (...)
        {
            this->locks_[needRangeIndex].clear(std::memory_order_release);
            throw;
        }

        this->locks_[needRangeIndex].clear(std::memory_order_release);
        return resultRange;
    }
} // namespace MemoryPool